package lc20240530;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description LRU缓存
 * @date 2024/5/30 9:15
 */
public class LRUCache {
    public static void main(String[] args) {
        LRUCache cache=new LRUCache(3);
        cache.put(1,1);
        cache.put(2,2);
        cache.put(4,4);
        cache.put(3,4);
        int i = cache.get(2);
        System.out.println(i);
    }

    int capacity;
    int size;
    Map<Integer,DoublyNode> map;
    DoublyNode head;
    DoublyNode tail;
    public LRUCache(int capacity){
        size=0;
        this.capacity=capacity;
        this.map=new HashMap<>();
        head=new DoublyNode();
        tail=new DoublyNode();
        head.next=tail;
        tail.prior=head;
    }
    public int get(int key){
        if (!map.containsKey(key)){
            return -1;
        }
        DoublyNode node=map.get(key);
        movetoHead(node);
        return node.val;
    }
    public void put(int key,int value){
        if (map.containsKey(key)){
            //更新为新value
            DoublyNode node=map.get(key);
            node.val=value;
            movetoHead(node);
        }else {
            DoublyNode newNode=new DoublyNode(key,value);
            map.put(key,newNode);
            addNode(newNode);
            if (size>capacity){
                DoublyNode node=popTail();
                map.remove(node.key);
            }
        }
    }
    public void movetoHead(DoublyNode node){
        removeNode(node);
        addNode(node);
    }
    public void addNode(DoublyNode node){
        head.next.prior=node;
        node.next=head.next;

        head.next=node;
        node.prior=head;
//        node.prior = head;
//        node.next = head.next;
//
//        head.next.prior = node;
//        head.next = node;
        size++;
    }

    public void removeNode(DoublyNode node){
        DoublyNode prev=node.prior;
        DoublyNode next=node.next;

        prev.next=next;
        next.prior=prev;
        size--;
    }
    public DoublyNode popTail(){
        DoublyNode res=tail.prior;
        this.removeNode(res);
        return res;
    }
}
